package com.dh.leetcode.one;

import com.dh.leetcode.common.ListNode;
import org.junit.Test;

/**
 * @ClassName: _147_Insertion_sort_list
 * @Description: 147. 对链表进行插入排序
 * <p>
 * https://leetcode-cn.com/problems/insertion-sort-list/
 * @Author: shouzimu
 * @Date: 2020/11/20 10:26
 */
public class _147_Insertion_sort_list {
    /**
     * 性能低的一批，但是也不想优化了
     * @param head
     * @return
     */
    public ListNode insertionSortList(ListNode head) {
        ListNode first = head;
        if (null == head || head.next == null) {
            return head;
        }

        int index = 1;
        head = head.next;
        while (null != head) {
            //record current record
            ListNode current = head;
            ListNode front = first;
            //断链
            while (front.next != current) {
                front = front.next;
            }
            front.next = current.next;
            head = current.next;

            front = first;
            int k = current.val;
            ListNode prev = null;
            boolean swap = false;
            for (int i = 0; i < index; i++) {
                if (front.val > k) {
                    //swap
                    current.next = front;
                    if (front == first) {
                        first = current;
                    }
                    if (null != prev) {
                        prev.next = current;
                    }
                    swap = true;
                    break;
                }
                prev = front;
                front = front.next;
            }
            if (!swap) {
                current.next = front;
                prev.next = current;
            }
            index++;
        }
        return first;
    }

    @Test
    public void insertionSortListTest() {
        ListNode head = ListNode.initNode(new int[]{-1, 5, 3, 4, 0});
        insertionSortList(head).print();
        head = ListNode.initNode(new int[]{4, 3, 1, 2});
        insertionSortList(head).print();
    }
}
